Communication networks, such as optical and data networks, utilize switch elements, such as a three-stage Clos switch, to direct connections between other switch elements located at other nodes. Network connections are coupled to each of the switch element inputs and outputs, so that data carried on any input line of a switch element can be switched to any output line on the same switch element. The switch elements include means to program the input to output connections. Networks are constantly changing in terms of connections, such as by adding/dropping connections, rerouting connections responsive to fault conditions, and the like. Invariably, the switch element is required to shift connections from one output line to another as the network changes, and the switch element in a network must be appropriately reconfigured or rearranged.
Switching events require the network connections across the switch element to be manipulated. Due to the number of connections across a single switching element, compensating for a switching event can be a complex and computationally intensive procedure. Examples of switching events include instances when network connections are added to a switch element already in use or instances when one of the links between network elements fails and another route through the network element is needed. When switching events require new connections to be formed, conventional switch elements must reconfigure the entire switch element. Many switch elements include devices, which are grouped into one of three stages of a three stage Clos array (e.g., within an ingress stage, a center stage or an egress stage). Typically, in response to switching events all of the switching devices (including those related to connections that are not directly affected by the switching event) within each of the stages of the array need to be reconfigured to form new connections through the switch element.
Referring to FIG. 1, a logical model 10 of an exemplary three-stage switch is illustrated. The logical model 10 includes input sorters 12a,12b with lines statically mapped to one or more input routers 14a,14b,14c,14d. The one or more input routers 14a,14b,14c,14d each include lines to each of one or more center switches 16a,16b which in turn include lines to each of one or more output routers 18a,18b,18c,18d. The output routers 18a,18b,18c,18d include lines statically mapped to output sorters 20a,20b. In an exemplary embodiment, the logical model includes 32 input sorters 12, 512 input routers 14, 24 center switches 16, 512 output routers 18, and 32 output sorters 20.
Conventionally, the algorithm for switch programming is a router-based algorithm. The router size is identical to the number of center stage switches and it must either be a factor of the line size or contain the line. For example, in the logical model 10 includes 24 center switches 16 because 24 is a factor of a line size 48 and 192, and 24 contains line sizes 3 and 13. Note, line sizes 3, 12, 48, and 192 correspond to SONET OC-3, OC-12, OC-48, and OC-192 and SDH STM-1, STM-4, STM-16, and STM-64. The sorters 12,20 allow timeslots in the line to be arbitrarily remapped. Since each line is mapped to one or more routers 14,18, the timeslots in the sorters 12,20 can be mapped to be input to the routers 14,18 is some specific order for the need of the switch control algorithm. An example of a router-based algorithm is illustrated in commonly-assigned U.S. Pat. No. 7,106,729 issued Sep. 12, 2006, and entitled “SWITCHING CONTROL MECHANISM BASED UPON THE LOGICAL PARTITIONING OF A SWITCH ELEMENT,” the contents of which are incorporated in-full by reference herein.
The parameters associated with the logical model are:
VariableDescriptionNcNumber of logical center stage switchesusedNiNumber of ingress routersNeNumber of egress routersNsNumber of sortersNfNumber of routers per sorterNr,maxMaximum number of routers per sorterScSize of a logical center switchSiSize of an ingress routerSeSize of an egress routerSfabric, logUsable switching capacity of the logicalfabricTmax, logMaximum number of inputs and outputsIn an exemplary embodiment of the logical model 10, Nc=24, Ni=Ne=512, Ns=32, Nr=16, Nr,max=18, Sc=Ni=Ne=512, and Si=Se=Nc=24. The usable switch capacity, Sfabric, log, equals Si·Sc=Se·Sc=12288. The maximum number of inputs and outputs, Tmax, log, equals Ns·Nf·Si=Ns·Nf·Se=12288.
The logical model 10 corresponds to a physical model of a switch. The sorters 12,20 correspond to line modules (LM) which include ports for inputs and outputs of lines. The center switches 16 correspond to physical center stage switches. For example, the LMs can connect to each of one or more center stage switches through a backplane. In an exemplary embodiment, the maximum number of physical inputs and outputs, Tmax, phy, equals 12288, i.e. the same as Tmax, log. Additionally, a physical center stage switch can support a switching fabric, Sfabric, phy, of 17280 which is less than Sfabric,log. The number of timeslots per physical link, Ts, can be equal to 18 which is less than Nr. The maximum number of inputs and outputs of the logical model (12288) matches exactly with the maximum number of timeslots to be supported in the physical switch (12288). The center stage switch capacity (12288) matches with the maximum number of inputs and outputs (12288) and only needs to use a fraction of available physical switch capacity (17280). The number of inputs and outputs per sorter (384) matches with the maximum number of timeslots in a LM (384) card. The number of routers per sorter (16) is less than the number of timeslots per link (18). And the size of the router (24) is less than the number of links between center stage switching chips and ingress/egress switching chips (30 and 32).
As such, this logical model 10 can fully represent the physical switch. The logical model 10 fulfills the requirements of switching timeslots (or wavelengths) through the center switch in a rearrangeably, non-blocking fashion. This model 10 provides the framework to pre-establish all connections while maintaining certain properties so that a protection switch for different upper layer applications can be done without a connection rearrangement calculation.
The center stage switching chips and ingress/egress switching chips have two fabric configuration banks, an active and a standby back. Configuration commands can be written to either bank at any time. Active bank updates are generally not hitless because the ingress, center, and egress switching chips cannot be written simultaneously. The traffic hit, if any, happens only on the connection being updated, and not on other connections. A hitless update is achieved by writing the new configuration to the standby bank and then doing a global active/standby bank swap, hereinafter referred to as a chain pull. All switching chips change banks on the next switch frame boundary after a chain pull. It is not possible to change the bank on just one switching chip; the chain pull is a global operation. Performing a chain pull involves hardware and software operations on ingress, egress, and center stage switches on switch module (SM) and LM modules. To protect against backplane glitches triggering a chain pull, each LM must arm its chain pull circuit before the SM strobes a global chain pull line. Hence the chain pull is operation is costly operation in terms of time it consumes to perform the operation. This has a direct effect on the mesh restoration times of different sub network connections.
Referring to FIG. 2, an exemplary switch control algorithm to program the switch fabric is Paull's algorithm. It provides a method of arranging a full set of input-to-output connections for a logical switch fabric. FIG. 2 illustrates Paull's matrix 30 representation for a three-stage switch. The ingress switches (or routers) index the rows of Paull's matrix 30. The egress switches (or routers) index the columns of Paull's matrix 30. The elements, symbols, in Paull's matrix 30 represent center switches. For a three-stage switch, such as the one in FIG. 1, consider any switch A in the input stage and any switch B in the output stage. An input to switch A can be connected to an output of B via any center stage switch, say F. Paull's connection matrix 30 represents this connection by entering the middle switch F into the (A, B) entry of the r×r matrix 30, where r is the number of input/output switches. In Paull's matrix multiple symbols may reside in any (A, B) entry. This corresponds to having multiple connections between the ingress switch A and the egress switch B.
For a valid connection matrix, each row can have at most m symbols (m represents the size of the ingress/egress switches), since there can be at most as many paths through an ingress switch as there are inputs to that switch. Each column can have at most m symbols, since there can be at most as many paths through an egress switch as there are outputs of that switch. The symbols in each row must be distinct, since there is only one edge from the egress stage switch to any center stage switch, and multi-casting to a different egress stage switches from a center stage switch is not allowed. The symbols in each column must be distinct, since there is only one edge between a center stage switch and an egress stage switch, and an edge cannot carry signals from two different inputs. In terms of performance of Paull's algorithm, the time spent on adding a single connection is non-deterministic because the nature of the algorithm requires searching for symbols in Paull's matrix in a manner of extending chains. The length of the chain is non-deterministic.
Disadvantageously, for every connection setup chain pull operation is required which is costly operation in terms of time it consumes to perform the operation. This has a direct effect on the mesh restoration times of different sub network connections. Also for every connection setup, Paull's rearrangement algorithm is run which is time consuming depending on how many connections get rearranged. In terms of performance of Paull's algorithm, the time spent on adding a single connection is non-deterministic because the nature of the algorithm requires searching for symbols in Paull's matrix in a manner of extending chains and the length of the chain is non-deterministic. Conventional router-based algorithms do not allow a switch to setup drop and continue and multicast connections easily. It is very cumbersome to setup those connections and also to change (modify) them when needed. Arbitrary timeslots must be reserved for setting up any arbitrary connections which involves multicast and drop-and-continue kind of connections. Also setup and maintenance of unidirectional connections is complex. Single timeslots could not be shared between more than one connections which are setup at two different times. This makes it extremely difficult to setup and manage test access point (TAP) connections and connection loopbacks especially on those connections which had some kind of protection scheme. Finally, line based switching scheme and path based switching schemes cannot co-exist at the same time for any timeslot.